/********************************************************************************
* @author: Liu  HZ
* @date: 2024/10/12
* @description: LeetCode-动态规划-基础版
********************************************************************************/

#ifndef THE_PATH_OF_CPP_DP_BASIC_H
#define THE_PATH_OF_CPP_DP_BASIC_H
////////////////////////////////////////////斐波那契类型//////////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming
 * 70. 爬楼梯
 */
int climbStairs(int n) {
    int i = 0, j = 0, ans = 1;

    for (int k = 1; k <= n; k++) {
        i = j;
        j = ans;
        ans = i + j;
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/fibonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming
 * 509. 斐波那契数
 */
int fib(int n) {
    int i = 0, j = 1, ans = 0;
    for (int k = 1; k <= n; k++) {
        i = j;
        j = ans;
        ans = i + j;
    }

    return ans;
}

/*
 * https://leetcode.cn/problems/n-th-tribonacci-number/?envType=study-plan-v2&envId=dynamic-programming
 * 1137. 第 N 个泰波那契数
 */
int tribonacci(int n) {
    int i = 0, j = 1, s = 1, ans = 2;

    if (n == 1 || n == 2)
        return 1;
    for (int k = 3; k <= n; k++) {

        ans = i + j + s;
        i = j;
        j = s;
        s = ans;
    }

    return n ? ans : 0;
}

/*
 * https://leetcode.cn/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming
 * 746. 使用最小花费爬楼梯
 */
int minCostClimbingStairs(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n + 1);
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

/*
 * https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=dynamic-programming
 * 198. 打家劫舍
 */
int rob(vector<int> &nums) {
    if (nums.empty()) {
        return 0;
    }
    int n = nums.size();
    if (n == 1) {
        return nums[0];
    }
    vector<int> dp = vector<int>(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[n - 1];
}

/*
 * https://leetcode.cn/problems/delete-and-earn/description/?envType=study-plan-v2&envId=dynamic-programming
 * 740. 删除并获得点数
 */
int deleteAndEarn(vector<int> &nums) {
    int maxVal = 0;
    for (int val: nums) {
        maxVal = max(maxVal, val);
    }
    vector<int> sum(maxVal + 1);
    for (int val: nums) {
        sum[val] += val;
    }
    return rob(sum);
}
/////////////////////////////////////////////////矩阵类型/////////////////////////////////////////////////////////////////
/*
 * https://leetcode.cn/problems/unique-paths/description/?envType=study-plan-v2&envId=dynamic-programming
 * 62. 不同路径
 */
int uniquePaths(int m, int n) {
    vector<vector<int>> f(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        f[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        f[0][j] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

/*
 * https://leetcode.cn/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=dynamic-programming
 * 64. 最小路径和
 */
int minPathSum(vector<vector<int>> &grid) {
    if (grid.size() == 0 || grid[0].size() == 0) {
        return 0;
    }
    int rows = grid.size(), columns = grid[0].size();
    auto dp = vector<vector<int> >(rows, vector<int>(columns));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < rows; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < columns; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < columns; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[rows - 1][columns - 1];
}

/*
 * https://leetcode.cn/problems/unique-paths-ii/?envType=study-plan-v2&envId=dynamic-programming
 * 63. 不同路径 II
 */
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
    int row = obstacleGrid.size(), col = obstacleGrid[0].size();
    vector<int> dp(col);

    // 判断起点是否是障碍物
    dp[0] = (obstacleGrid[0][0] == 0);
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            // 如果当前位置是障碍物, 则置为0
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
                continue;
            }

            if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                dp[j] += dp[j - 1];
            }
        }
    }

    return dp.back();
}

/*
 * https://leetcode.cn/problems/triangle/?envType=study-plan-v2&envId=dynamic-programming
 * 120. 三角形最小路径和
 */
int minimumTotal(vector<vector<int>> &triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n));
    dp[0][0] = triangle[0][0];

    for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][0] + triangle[i][0];
        for (int j = 1; j < i; ++j) {
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
        }
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
    }

    return *min_element(dp[n - 1].begin(), dp[n - 1].end());
}

#endif //THE_PATH_OF_CPP_DP_BASIC_H
